#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * @brief The Solution class 198. 打家劫舍
 */
class Solution {

public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1) return nums[0];

        int dp[n];

        dp[0] = nums[0];
        dp[1] = std::max(nums[0],nums[1]);
        for(int i=2; i < n; i++)
        {
            dp[i] = std::max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
};

namespace Merge {

void _combine(vector<int>& nums, int left, int mid, int right, vector<int>& temp)
{
    int i = left;
    int j = mid + 1;
    int k = 0;

    while(i <= mid || j <= right)
    {
        if(i <= mid && j <= right)
        {
            // 两个数组都还有值
            if(nums[i] == nums[j])
            {
                temp[k++] = nums[i];
                temp[k++] = nums[j];
                j++;
                i++;
            } else if(nums[i] < nums[j])
            {
                // 仅第一个数组有值
                temp[k++] = nums[i];
                i++;
            }else if(nums[j] < nums[i])
            {
                // 仅第二个数组有值
                temp[k++] = nums[j];
                j++;
            }
        } else if(i <= mid)
        {
            temp[k++] = nums[i];
            i++;
        } else if(j <= right)
        {
            temp[k++] = nums[j];
            j++;
        }
    }

    // 拷贝整理好的数据到原始数组中
    for(int pos = 0; pos < k; pos++)
    {
        nums[left + pos] = temp[pos];
    }

}

void _merge(vector<int>& nums,int i, int j, vector<int>& temp)
{
    if(i < j)
    {
        // 二分区域，细化到范围为2为止
        int mid = i + (j-i)/2;

        _merge(nums,i,mid,temp);
        _merge(nums,mid+1,j,temp);

        // 合并两个有序数组
        _combine(nums,i,mid,j,temp);
    }
}

/**
 * @brief sort 归并算法排序
 * @param nums 乱序数组
 */
void sort(vector<int>& nums)
{
    int n = nums.size();
    vector<int> temp(n);
    _merge(nums, 0, n-1, temp);
}

}


//int main()
//{
////    cout << "Hello World!" << endl;
////    Solution solution;
////    vector<int> nums;
////    nums.push_back(1);
////    nums.push_back(2);
////    nums.push_back(3);
////    nums.push_back(1);
////    int rob = solution.rob(nums);
////    cout << "End rob: " << rob << endl;

//    int n = 1000;
//    vector<int> nums(n);
//    for(int i = 0; i < n; i++)
//    {
//        nums[i] = n - i;
//    }
//    Merge::sort(nums);
//    cout << "nums[0] = " << nums[0] << endl;
//    cout << "nums[1] = " << nums[1] << endl;
//    cout << "nums[2] = " << nums[2] << endl;

//}
